#include <bits/stdc++.h>
using namespace std;

inline int read() {
	int x = 0, f = 0; char ch = getchar();
	while (ch < '0' or ch > '9') f |= (ch == '-'), ch = getchar();
	while (ch >= '0' and ch <= '9') x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
	return f ? -x : x;
}

int __stk[128], __top;
inline void write(int x) {
    if(x < 0) putchar('-'), x = -x;
	do { __stk[++__top] = x % 10, x /= 10; } while (x);
	while (__top) putchar(__stk[__top--] + '0');
}

int mod = 998244353;

void Min(int &x, int y) { y < x and (x = y); }
void Max(int &x, int y) { y > x and (x = y); }

void inc(int &x, int y) { (x += y) >= mod and (x -= mod); }
void mul(int &x, int y) { x = 1ll * x * y % mod; }

int q_pow(int x, int k) { int res = 1; for (; k; k >>= 1, mul(x, x)) if (k & 1) mul(res, x); return res; }

bool stmer;

const int N = 1 << 23;

int n, m, k;
int f[N], g[N], fac[N], inv[N];

int C(int x, int y) { return y > x ? 0 : 1ll * fac[x] * inv[y] % mod * inv[x - y] % mod; }

void init() {
	fac[0] = 1;
	for (int i = 1; i < N; i++) fac[i] = 1ll * fac[i - 1] * i % mod;
	inv[N - 1] = q_pow(fac[N - 1], mod - 2);
	for (int i = N - 1; i; i--) inv[i - 1] = 1ll * inv[i] * i % mod;
}

namespace NTT {
	const int g = 3;
	
	int tmp, R[N];
	void init(int len) {
		for(int i = 1; i < len; i++) R[i] = (R[i >> 1] >> 1) + (i & 1) * (len >> 1);
	}
	void ntt(int *f, int len, int op) {
		init(len);
		for(int i = 0; i < len; i++) if(i < R[i]) swap(f[i], f[R[i]]);
		for(int i = 1; i < len; i += i) {
			int ad = q_pow(op ? g : ((mod + 1) / g), (mod - 1) / (i << 1));
			for(int j = 0; j < len; j += (i << 1)) {
				int w = 1; for(int k = 0; k < i; k++, w = 1ll * w * ad % mod)
				tmp = 1ll * w * f[i + j + k] % mod, f[i + j + k] = (f[j + k] - tmp + mod) % mod, f[j + k] = (f[j + k] + tmp) % mod;
			}
		}
		if(!op) for(int i = 0, invn = q_pow(len, mod - 2); i < len; i++) f[i] = 1ll * f[i] * invn % mod;
	}
}

namespace sub1 {
	void main() {
		int len = 1, k = m; g[0] = 1;
		while (len <= n) len <<= 1; len <<= 1;
		
		NTT :: ntt(f, len, 1), NTT :: ntt(g, len, 1);
		for (; k; k >>= 1) {
			if (k & 1) {
				for (int i = 0; i < len; i++) mul(g[i], f[i]);
				NTT :: ntt(g, len, 0);
				for (int i = n + 1; i < len; i++) g[i] = 0;
				NTT :: ntt(g, len, 1);
			}
			for (int i = 0; i < len; i++) mul(f[i], f[i]);
			NTT :: ntt(f, len, 0);
			for (int i = n + 1; i < len; i++) f[i] = 0;
			NTT :: ntt(f, len, 1);
		}
		NTT :: ntt(g, len, 0), mul(g[n], fac[n]);

		write(g[n]), putchar('\n');
	}
}

namespace sub2 {
	void main() {
		int ans = 0; g[0] = 1;

		for (int i = 1; i <= min(n, m); i++) {
			for (int j = n; j + 1; j--) {
				for (int k = 1; j + k <= n; k++) inc(g[j + k], 1ll * g[j] * f[k] % mod);
				g[j] = 0;
			}
			inc(ans, 1ll * g[n] * C(m, i) % mod * q_pow(f[0], m - i) % mod * fac[n] % mod);
		}
		
		write(ans), putchar('\n');
	}
}

bool edmer;
signed main() {
	freopen("sequence.in", "r", stdin);
	freopen("sequence.out", "w", stdout);
	cerr << "[Memory] " << (&stmer - &edmer) / 1024 / 1024 << " MB\n";

	n = read(), m = read(), k = read(), mod = read();

	init();

	for (int i = 0; i <= n; i++) {
		if (i + k < 0) continue;
		f[i] = 1ll * q_pow(i, i + k) * inv[i] % mod;
	}

	if (mod == 998244353) sub1 :: main();
	else sub2 :: main();

    cerr << "[Runtime] " << (double) clock() / CLOCKS_PER_SEC << " seconds\n";
	return 0;
} 